\documentclass[a4paper]{article}
\usepackage{geometry}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage{subfigure}
\usepackage{indentfirst}
\usepackage{makecell}

\title{An Implmentation of the Boolean Algebra For Yin Sets}
\author{Zhixuan Li}

\newtheorem{prop}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}

\newcommand{\bJ}{\mathbb{J}}
\newcommand{\bJpl}{\mathbb{J}^{pl}}
\newcommand{\zerohat}{\hat{0}}
\newcommand{\onehat}{\hat{1}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\loc}[1]{\text{loc}(#1)}
\newcommand{\bigO}[1]{\mathcal{O}(#1)}

\begin{document}
\maketitle

\section{Algorithm}

\begin{definition}
  The subspace $\bJpl$ of the Jordan space $\bJ$
  contains $\{\zerohat\}$, $\{\onehat\}$
  and all the spadjor forests whose realizable spadjor is a set of oriented polygons.
\end{definition}

\begin{definition}
If $P$ is a polygon, denote by $\vert P \vert$ the number of vertices of $P$. 
If $\cF \in \bJpl$, $\vert \cF \vert := \sum_{P \in \cJ(\cF)} \vert P \vert$.
In particular, $\vert\{\zerohat\} \vert = \vert \{\onehat\}  \vert = 0$.
\end{definition}

\subsection{The Locater}
Given a point and a Yin set in the plane,
there are three possibilities for the relative location of this point to the Yin set, 
i.e. interior, exterior and on boundary.
Based on the idea of the line sweep alogorithm \cite{CG},
Algorithm \ref{alg:locate} is designed as follows.

\begin{algorithm}[htbp]
  \caption{locate($\cF,P$) : Compute the relative locations of a set of points}
  \label{alg:locate}
  \begin{algorithmic}[1]
    \renewcommand{\algorithmicrequire}{\textbf{Input : }}
    \REQUIRE A non-trivial $\cF \in \bJpl$.
    A set of query points $P = \{p_1,\cdots,p_q\}$.
    % \renewcommand{\algorithmicrequire}{\textbf{Precondition : }}
    % \REQUIRE None.
    \renewcommand{\algorithmicensure}{\textbf{Output : }}
    \ENSURE The relative locations $\loc{p}, \forall p \in P$.
    % \renewcommand{\algorithmicensure}{\textbf{Postcondition : }}
    % \ENSURE 
    \STATE Collapse $\cF$ into a set of directed segments $S = \{s_1,\cdots,s_n\}$. 
    \STATE Initiailize the ordered set $Q$
    to contain the endpoints of all the segments in $S$,
    as well as the query points. 
    \STATE Denote the set of segments whose upper endpoint is $p$ as $U(p)$, 
    and $L(p)$ likewise. 
    \STATE Initialize the status structure $\mathcal{T}$ as empty. 
    \STATE
    
    \WHILE{$Q$ is not empty}
    \STATE Pop the front of $Q$, denoted as $p$. 
    \IF{$L(p) \cup U(p) \ne \emptyset$}
    \STATE Remove the segments in $L(p)$ from $\mathcal{T}$. 
    \STATE Add the segments in $U(p)$ to $\mathcal{T}$. 
    \IF{$p \in P$}
    \STATE $\loc{p} \leftarrow \text{OnBoundary}$. 
    \ENDIF
    \ELSE
    \STATE Denote the left and right neighbour of $p$
    in $\mathcal{T}$ by $s_l,s_r$ respectively. 
    \IF{neither $s_l$ nor $s_r$ exists}
    \STATE $\loc{p}$ is determined from whether $\rho(\cF)$ is bounded. 
    \ELSIF{$p \in s_l$ or $p \in s_r$}
    \STATE $\loc{p} \leftarrow \text{OnBoundary}$. 
    \ELSE
    \STATE $\loc{p}$ is determined from either
    \textbf{Left}($s_l,p$) or \textbf{Left}($s_r,p$). 
    \STATE /* \textbf{Left}($\{p_1 \rightarrow p_2\},q$) = $(p_2-p_1) \times (q-p_1) > 0$ */
    \ENDIF
    \ENDIF

    \ENDWHILE
  \end{algorithmic}
\end{algorithm}

\begin{prop}
  Algorithm \ref{alg:locate} correctly computes the relative locations.
\end{prop}
\begin{proof}
  The proof consists of two parts.
  First we prove that $\mathcal{T}$ records the segments
  in the order that they intersect with the sweep line
  from left to right.
  Next we show that for a particular query point,
  all possibilities are exhausted in the algorithm.
  WLOG we may assume $S$ does not contain horizontal segments.

  \begin{enumerate}
  \item The segments in $S$ do not overlap or intersect properly
    since they are collapsed from a realizable spadjor.
    It follows that during the presence of a segment in $\mathcal{T}$,
    it does not exchange position with other segments.
    Finally the appearance and disappearance of a segment
    in the line sweep process
    happens only at endpoints,
    and Line 9-10 handle that properly.
  \item
    If the current event point $p \in \mathcal{P}(\cF)$,
    then $p$ either coincides with an endpoint
    or lies in the interior of a segment.
    They are resolved in Line 11-13 and Line 18-19 respectively.
    Otherwise, by the definition of interior,
    the relative location of $p$ can be determined
    from any of the two neighbouring directed segments (Line 21).
    In the trivial case of $p$ not having a neighrbouring segment,
    its relative location depends on
    whether $\rho(\cF)$ is bounded (Line 17).
  \end{enumerate}
\end{proof}

\begin{prop}
  Algorithm \ref{alg:locate} takes time $\bigO{(n+q) \log n}$.
  Here $n = \vert \cF \vert$ and $q$ is the number of queries.
\end{prop}

%\begin{remark}
%  The complexity exactly matches our previous result
%  if we see the query points as degenerate segments
%  and notice that the number of intersection is bounded by $n+q$.
%\end{remark}

\subsection{The pasting map}

The implementation of the pasting map is listed in Algorithm \ref{alg:pasting}. 
If $\cJ$ is the output of the algorithm, and $\rho(\cJ)$ is topological simple, 
we may assume that 
the processing of each curve segment in $E$, 
the output of (MRS-d), 
has constant complexity. 
Under such assumption, 
the running time of Algorithm \ref{alg:pasting} is roughly linear to $\vert E \vert$. 
%We shall note, however, that $\vert E \vert$ and $I$
%are not bounded by each other. 

\begin{algorithm}[htbp]
  \caption{$\cJ$ = PastingMap($G$)}
  \label{alg:pasting}
  \begin{algorithmic}[1]
    \renewcommand{\algorithmicrequire}{\textbf{Input : }}
    \REQUIRE The directed multigraph $G=(V,E)$ output by the operation (MRS-d). 
    \renewcommand{\algorithmicensure}{\textbf{Output : }}
    \ENSURE A set of Jordan curves $\cJ$.
    \renewcommand{\algorithmicensure}{\textbf{Postcondition : }}
    \ENSURE $\cJ$ is a realizable spadjor.

    \STATE Initialize $\cJ$ as empty.
    \STATE Initialize $R$, a linear container of curve segments, as empty.

    \WHILE{true}
    \IF{$R = \emptyset$}
    \STATE Exit if $E = \emptyset$.
    \STATE Reset $\mathcal{P} \leftarrow \emptyset$.
    \STATE Select a non-isolated vertex $v_s \in V$.
    Select an arbitrary edge $s$ that starts from $v_s$.
    \ELSE
    \STATE Denote the last curve segment in $R$ as $s'$.
    \STATE Let $v_s$ be the end point of $s'$.
    \STATE Among the out-edges incident to $v_s$,
    select the out-edge $s$ to be the clockwise neighbour of $s'$. 
    \ENDIF
    \STATE Push back $s$ into $R$.
    \STATE $\mathcal{P} \leftarrow \mathcal{P} \cup \{v_s\}$.
    \STATE Let $v_e$ be the end point of $s$.
    \IF{$v_e \in \mathcal{P}$}
    % \STATE Extract the sequence of curve segments from $R$ that forms a loop
    % and make them a Jordan curve $\gamma$ % gamma <- seq of seg from R !!
    \STATE Let $R^{\circ} \subset R$ be the subset
    of curves segments that forms a loop.
    \STATE $R \leftarrow R \setminus R^{\circ}$.
    \STATE For each $q \in \mathcal{P}$, remove $q$ from $\mathcal{P}$
    if $q$ is on $R^{\circ}$ but not the start point of $R^{\circ}$.
    \STATE Construct a Jordan curve $\gamma$ by joining the curve segments in $R^{\circ}$.
    \STATE $\cJ \leftarrow \cJ \cup \{\gamma\}$.
    \ENDIF
    \STATE $E \leftarrow E \setminus \{s\}$. 
    \ENDWHILE
  \end{algorithmic}
\end{algorithm}

\subsection{The meet operation}
Suppose Let $\cJ_1, \cJ_2 \in \bJpl$ 
and we are to calculate $\cJ = \cJ_1 \wedge \cJ_2$. 
We shall need the symbols in Table \ref{tab:notation} in the complexity analysis. 

\begin{table}[htb]
  \centering
  \begin{tabular}{|c|l|}
  \hline
    $n$ & $\vert \cJ_1 \vert + \vert \cJ_2 \vert$.  \\
    \hline
    $V$ & the set of isolated points characterizing $\mathcal{P}(\cJ_1) \cap \mathcal{P}(\cJ_2)$.  \\
    \hline
    $I$ & $\vert V \vert$. \\
    \hline
    $k_0$ & \makecell[tl]{the total number of $\beta_i$ after the segmentation map $S_V$ is appled. \\
    It is bounded below by $I$.} \\
    \hline
    $E$ & \makecell[tl]{the set of curve segments output by (MRS-d). \\
    We have $\vert E\vert \le k_0$, 
    but in general $\vert E \vert$ and $I$ are not bounded by each other. }\\
%    \hline
%    $m$ & number of Jordan curves in $\cJ$.  \\
%    \hline
%    $l$ & $\max_{\gamma \in \cJ} \vert \gamma \vert$ . \\
    \hline
  \end{tabular}
  \caption{Notations. }
  \label{tab:notation}
\end{table}

\begin{enumerate}
\item (MRS-a) calculates the intersections of the Jordan curves in $\cJ_1$ and $\cJ_2$. 
It has complexity $\bigO{(n+I) \log n}$.
\item The segmentation map $S_V$ is performed in (MRS-b). It is of $\bigO{I}$.
\item (MRS-c) and (MRS-d) filter the output of $S_V$ and construct the set $E$ of curve segments. 
The function \textbf{locate()} is invoked here and it takes $\bigO{(n+k_0) \log n}$. 
\item The pasting map takes $\bigO{\vert E \vert}$ in normal cases. 
\end{enumerate}

To summarize, 
the meet operation has the complexity $\bigO{(n+k_0) \log n}$ in the worst case. 
In the normal cases when $\cJ_1, \cJ_2$ and $\cJ_1 \wedge \cJ_2$ are all topologically simple, 
we are safe to assume $k_0 = \bigO{I}$. 
Thus the complexity of the meet operation is bounded by $\bigO{(n+I) \log n}$, 
where the majority of the computation time 
is spent on calculating the intersections of line segments. 

\subsection{The complementation operation}

Suppose $\cJ \in \bJpl$ and we are to calculate $\cJ'$. 
Let $n = \vert \cJ \vert$. 
Reversing the orientations of each Jordan curve requires $\bigO{n}$ operations. 
Note that the segmentation map and the pasting map
operate on no more than $n$ curve segments, 
hence the complexities of which are bounded by $\bigO{n}$. 
Thus the complementation operation has the complexity $\bigO{n}$. 

\subsection{Constructing the Hasse Diagram}

\begin{definition}
Let $\cJ = \{\gamma_1,\cdots,\gamma_m\}$ be a non-empty realizable spadjor. 
  The directed graph induced by the covering relation on $\cJ$ is $G_{\cJ} = (V,E)$ where
  \begin{equation}
    \begin{aligned}
      V =& \left\{ 1,\cdots,m \right\},  \\
      E =& \left\{ (k,l) : \gamma_k \succ \gamma_l, 1 \le k,l \le m  \right\}.  \\
    \end{aligned}
  \end{equation}
\end{definition}

\newcommand{\BB}[1]{\text{BB}(#1)}

Recovering the Hasse diagram of a $\cJ \in \bJpl$ 
requires a topological sort on the directed graph induced by $G_{\cJ}$.
Details are listed in Algorithm \ref{alg:hasse}. 

\begin{algorithm}[htbp]
  \caption{buildHasse($\cJ$) : construct the Hasse diagram for $\cJ$}
  \label{alg:hasse}
  \begin{algorithmic}[1]
    \renewcommand{\algorithmicrequire}{\textbf{Input : }}
    \REQUIRE A non-empty realizable spadjor $\cJ = \{\gamma_1,\cdots,\gamma_m\}$.
    \renewcommand{\algorithmicensure}{\textbf{Output : }}
    \ENSURE The Hasse diagram of $\cJ$.
    
    \STATE For $i=1,\cdots,m$,
    let $p_i$ be an interior point
    in the bounded component of $\mathbb{R}^2 \setminus \gamma_i$. 
    \STATE Initialize $G_{\cJ} = (V,E)$ where 
    $V = \left\{1, \ldots, m\right\}$ and $E = \emptyset$.
    \STATE Let $Q_i = \{ 1 \le j \le m : j \ne i, \BB{\gamma_i} \supset \BB{\gamma_j} \}, 1 \le i \le m$. 
    $\BB{\cdot}$ is the bounding box function. 
    \STATE
    \FOR{$i = 1,\cdots,m$}
    \STATE Call \textbf{locate}($\{\gamma_i\}, \{p_j : j \in Q_i\}$).
    \STATE For each $j \in Q_i$, set $E \leftarrow E \cup \{(i, j)\}$ 
    if $p_j$ is in the bounded component of $\mathbb{R}^2 \setminus \gamma_i$. 
    \ENDFOR
    \STATE Return \textbf{TopologicalSort}($G_{\cJ}$). 
  \end{algorithmic}
\end{algorithm}

\begin{prop}
  Algorithm \ref{alg:hasse} takes time $\bigO{m(m+l)\log l}$ in the worst case, 
  where $m$ is the number of Jordan curves in a realizable spadjor
  and $l = \max_{\gamma \in \cJ} \vert \gamma \vert$.
\end{prop}


\bibliography{ref.bib}
\bibliographystyle{plain}

\end{document}
